/*
day360 
2020.8.22 
*/
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    int minSetSize(vector<int>& arr) {
		unordered_map<int,int> m;
		for(int &i:arr)
		{
			m[i]++;
		}
		
		vector<int> vec_size;
		for(auto &i : m)
		{
			vec_size.push_back(i.second);
		}
		
		sort(vec_size.begin(),vec_size.end());
		
//		for(int i=0;i<vec_size.size();++i)
//		{
//			cout<<vec_size[i]<<'\t';
//		}cout<<endl;
//		cout<<arr.size()<<endl;
		int res=0;
		int p=vec_size.size()-1,sum=0;
		while(sum*2<arr.size())
		{
			res++;
			sum+=vec_size[p];
			p--;
		}
		return res;
    }
};

int main()
{
	Solution s;
	vector<int> arr={3,3,3,3,5,5,5,2,2,7};
	cout<<s.minSetSize(arr)<<endl;
	return 0;
}
